---

deBST.hpp

Go to the documentation of this file.

///////////////////////////////////////////////////////////////////////////////
/// @file deBST.hpp
///
/// @brief Templated Binary Search Tree with chaining
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Apr 2002
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DEBST_HPP
#define DEBST_HPP

#include "deList.hpp"

#pragma warning (disable : 4710)

/// templated binary tree storage class
template <class T, long N>
class deTBST
{
private:
    class TBSTNode
    {
    public:
        TBSTNode(const T & ref, const DWORD Val[N])
            :Data(ref), Left(NULL), Right(NULL), Parent(NULL), Chain(NULL), BST(NULL)
        {
            memcpy(Value, Val, sizeof(DWORD)*N);
        }
        TBSTNode(const TBSTNode & ref)
            :Data(ref.Data), Left(NULL), Right(NULL), Parent(NULL), Chain(NULL), BST(NULL)
        {
            memcpy(Value, ref.Value, sizeof(DWORD)*N);
        }
        ~TBSTNode()
            {}
        bool operator ==(const DWORD Val[N])
        {
            for (int i = 0; i < N; i++)
            {
                if (Value[i] != Val[i])
                    return false;
            }
            return true;
        }
        bool operator >(const DWORD Val[N])
        {
            for (int i = 0; i < N; i++)
            {
                if (Value[i] <= Val[i])
                    return false;
            }
            return true;
        }
        bool operator <(const DWORD Val[N])
        {
            for (int i = 0; i < N; i++)
            {
                if (Value[i] >= Val[i])
                    return false;
            }
            return true;
        }
        void Destroy()
        {
            if (Left)
                Left->Destroy();
            if (Right)
                Right->Destroy();
            if (Chain)
                Chain->Destroy();
            delete this;
        }
        void AddDataToList(deTList <T*> &list)
        {
            list.AddElement(&Data);
            if (Chain)
                Chain->AddDataToList(list);
            if (Left)
                Left->AddDataToList(list);
            if (Right)
                Right->AddDataToList(list);
        }
        void AddValueToList(deTList <DWORD> &list)
        {
            list.AddElement(Value);
            if (Left)
                Left->AddValueToList(list);
            if (Right)
                Right->AddValueToList(list);
        }

        TBSTNode *Left, *Right;
        TBSTNode *Parent, *Chain;
        deTBST * BST;
        T Data;
        DWORD Value[N];
/*      //Temp fix for the crash when deleting
        void *operator new (size_t Size)
        {
            return malloc(Size);
        }
        void operator delete (void *p)
        {
            free(p);
            return;
        }
*/  };

public:
    class iterator
    {
    private:
        friend class deTBST<T,N>;
        TBSTNode* m_Node;
    protected:
        iterator(TBSTNode* node) : m_Node(node) {}
    public:
        iterator() : m_Node(NULL) {}
        ~iterator() {}
        T& operator*() const
        {
            DE_ASSERT (m_Node != 0);
            return m_Node->Data;
        }
        T* operator->() const { return &operator*(); }
        void operator++()
        {
            TBSTNode *Node = m_Node;
            if (Node->Chain)
            {
                Node = Node->Chain;
            }
            else
            {
                while (Node->Parent && Node->Parent->Chain == Node)
                    Node = Node->Parent;
                if (Node->Right)
                {
                    Node = Node->Right;
                    while (Node->Left)
                        Node = Node->Left;
                }
                else if (Node->Parent)
                {
                    while (Node && Node->Parent && Node == Node->Parent->Chain)
                        Node = Node->Parent;
                    while (Node && Node->Parent)
                    {
                        if (Node->Parent->Left == Node)
                        {
                            Node = Node->Parent;
                            break;
                        }
                        else
                        {
                            Node = Node->Parent;
                            if (!Node->Parent)
                                Node = NULL;
                        }
                    }
                }
                else
                    Node = NULL;
            }
            m_Node = Node;
        }
        //void operator--() { m_Node = m_Node->Prev; }
        bool operator==(const iterator & other) const
        { return m_Node == other.m_Node; }
        bool operator!=(const iterator & other) const
        { return m_Node != other.m_Node; }
    };

private:
    TBSTNode * m_Root;
    long m_Length;

public:
    deTBST()
    {
        m_Root = NULL;
        m_Length = 0;
    }
    deTBST(const deTBST <T, N> & ref)
    {
        m_Root = NULL;
        m_Length = 0;

        TBSTNode * Node = ref.m_Root;
        while(Node)
        {
            AddElement(Node->Data, Node->Value);
            Node = Node->Left;
        }
    }
    const deTBST <T, N> & operator=(const deTBST <T, N> & ref)
    {
        // not implemented
        throw;

        EmptyBST();
        
        return *this;
    }
    ~deTBST()
    {
        EmptyBST();
    }

    void EmptyBST()
    {
        if (m_Root)
            m_Root->Destroy();
        m_Root = 0;
        m_Length = 0;
    }

    void* GetRoot(T* &obj, DWORD value[N]) const
    {
        TBSTNode *Node = m_Root;
        obj = NULL;
        if (!Node)
        {
            return NULL;
        }
        obj = &(Node->Data);
        if (value)
            memcpy(value, Node->Value, N);
        return Node;
    }
    void* FindValue(const DWORD Val[N], T* &obj) const
    {
        TBSTNode *Node = m_Root;
        while (Node)
        {
            if (*Node == Val)
                break;
            if (*Node > Val)
                Node = Node->Left;
            else
                Node = Node->Right;
        }
        obj = NULL;
        if (!Node)
        {
            return NULL;
        }
        if (Node)
            obj = &(Node->Data);
        return Node;
    }
    void* FindValue(const DWORD Val[N], T & obj) const
    {
        T * objptr;
        void * ptr;
        ptr = FindValue(Val, objptr);
        if (objptr)
            obj = *objptr;
        return ptr;
    }
    void * GetLeftMost(T* &obj, DWORD value[N])
    {
        TBSTNode *Node = (TBSTNode*)m_Root;
        obj = NULL;
        if (!Node)
        {
            return NULL;
        }
        while (Node->Left)
            Node = Node->Left;
        if (Node)
        {
            obj = &(Node->Data);
            if (value)
                memcpy(value, Node->Value, N);
        }
        return Node;
    }
    void * GetLeftMostLeaf(T* &obj, DWORD value[N])
    {
        TBSTNode *Node = (TBSTNode*)m_Root;
        obj = NULL;
        if (!Node)
        {
            return NULL;
        }
        while (Node->Left || Node->Right)
        {
            if (Node->Left)
                Node = Node->Left;
            Node = Node->Right;
        }
        if (Node)
        {
            obj = &(Node->Data);
            if (value)
                memcpy(value, Node->Value, N);
        }
        return Node;
    }
    void * GetLeftMost(T &obj, DWORD value[N])
    {
        T * objptr;
        void * ptr;
        ptr = GetLeftMost(objptr, value);
        if (objptr)
            obj = *objptr;
        return ptr;
    }
    void * GetNextRight(void * current, T* &obj, DWORD value[N])
    {
        TBSTNode *Node = (TBSTNode*)current;
        obj = NULL;
        if (!Node)
        {
            return NULL;
        }
        if (Node->Right)
        {
            Node = Node->Right;
            while (Node->Left)
                Node = Node->Left;
        }
        else if (Node->Parent)
        {
            while (Node && Node->Parent && Node == Node->Parent->Chain)
                Node = Node->Parent;
            while (Node && Node->Parent)
            {
                if (Node->Parent->Left == Node)
                {
                    Node = Node->Parent;
                    break;
                }
                else
                {
                    Node = Node->Parent;
                    if (!Node->Parent)
                        Node = NULL;
                }
            }
        }
        else
            Node = NULL;
        if (Node)
        {
            obj = &(Node->Data);
            if (value)
                memcpy(value, Node->Value, N);
        }
        return Node;
    }
    void * GetNextRight(void * current, T &obj, DWORD value[N])
    {
        T * objptr;
        void * ptr;
        ptr = GetNextRight(current, objptr, value);
        if (objptr)
            obj = *objptr;
        return ptr;
    }
    void* GetNextChain(void* current, T* &obj) const
    {
        TBSTNode *Node = (TBSTNode*)current;
        obj = NULL;
        if (!Node || !Node->Chain)
        {
            return NULL;
        }
        Node = Node->Chain;
        if (Node)
            obj = &(Node->Data);
        return Node;
    }
    void* GetNextChain(void* current, T & obj) const
    {
        T * objptr;
        void * ptr;
        ptr = GetNextChain(current, objptr);
        if (objptr)
            obj = *objptr;
        return ptr;
    }
    void* AddElement(const T & data, const DWORD Val[N])
    {
        TBSTNode *Node, *NewNode = new TBSTNode(data, Val);
        if (!NewNode)
            return NULL;

        NewNode->BST = this;
        m_Length++;
        if (m_Root == NULL)
            m_Root = NewNode;
        else
        {
            Node = m_Root;
            while (Node != NULL)
            {
                if (*Node == Val)
                {
                    while (Node->Chain != NULL)
                        Node = Node->Chain;
                    Node->Chain = NewNode;
                    NewNode->Parent = Node;
                    break;
                }
                else
                if (*Node > Val)
                {
                    if (Node->Left)
                    {
                        Node = Node->Left;
                    }
                    else
                    {
                        Node->Left = NewNode;
                        NewNode->Parent = Node;
                        break;
                    }
                }
                else
                {
                    if (Node->Right)
                    {
                        Node = Node->Right;
                    }
                    else
                    {
                        Node->Right = NewNode;
                        NewNode->Parent = Node;
                        break;
                    }
                }
            }
        }

        return NewNode;
    }
    static void StaticRemoveElement(void * ptr)
    {
        TBSTNode * Node = (TBSTNode*)ptr;
        if (Node->BST)
            Node->BST->RemoveElement(ptr);
    }
//#pragma todo (make sure RemoveElement really works) // I think it does
    deBoolean RemoveElement(void * ptr)
    {
        TBSTNode * Node = (TBSTNode*)ptr;
        if (Node == NULL)
            return deFALSE;

        // if we have a chain, can just shift the next link up into this node's spot
        if (Node->Chain)
        {
            // point the chain at our left child and the child at the chain
            if (Node->Left)
            {
                Node->Chain->Left = Node->Left;
                Node->Left->Parent = Node->Chain;
            }
            // point the chain at our right child and the child at the chain
            if (Node->Right)
            {
                Node->Chain->Right = Node->Right;
                Node->Right->Parent = Node->Chain;
            }
            // if we aren't the root, then the parent needs to update its linkage
            if (Node->Parent)
            {
                Node->Chain->Parent = Node->Parent;
                if (Node->Parent->Chain == Node)
                {
                    Node->Parent->Chain = Node->Chain;
                }
                else if (Node->Parent->Left == Node)
                {
                    Node->Parent->Left = Node->Chain;
                }
                else if (Node->Parent->Right == Node)
                {
                    Node->Parent->Right = Node->Chain;
                }
            }
            else
                m_Root = Node->Chain;
        }
        else if (Node->Left || Node->Right)
        {
            // we have children
            if (Node->Right == NULL)
            {
                // only have a left node
                Node->Left->Parent = Node->Parent;
                if (Node->Parent)
                {
                    if (Node->Parent->Chain == Node)
                    {
                        Node->Parent->Chain = Node->Left;
                    }
                    else if (Node->Parent->Left == Node)
                    {
                        Node->Parent->Left = Node->Left;
                    }
                    else if (Node->Parent->Right == Node)
                    {
                        Node->Parent->Right = Node->Left;
                    }
                }
                else
                    m_Root = Node->Left;
            }
            else if (Node->Left == NULL)
            {
                // only have a right node
                Node->Right->Parent = Node->Parent;
                if (Node->Parent)
                {
                    if (Node->Parent->Chain == Node)
                    {
                        Node->Parent->Chain = Node->Right;
                    }
                    else if (Node->Parent->Left == Node)
                    {
                        Node->Parent->Left = Node->Right;
                    }
                    else if (Node->Parent->Right == Node)
                    {
                        Node->Parent->Right = Node->Right;
                    }
                }
                else
                    m_Root = Node->Right;
            }
            else
            {
                // have two children. This is the "Nasty Case"
                TBSTNode * tempNode = Node->Right;
                while (tempNode->Left)
                {
                    tempNode = tempNode->Left;
                }
                // now we have the smallest value that's greater than value in 'Node'
                {
                    // first move its right child into place
                    if (tempNode->Right)
                        tempNode->Right->Parent = tempNode->Parent;
                    if (Node->Parent)
                    {
                        if (tempNode->Parent->Chain == tempNode)
                        {
                            tempNode->Parent->Chain = tempNode->Right;
                        }
                        else if (tempNode->Parent->Left == tempNode)
                        {
                            tempNode->Parent->Left = tempNode->Right;
                        }
                        else if (tempNode->Parent->Right == tempNode)
                        {
                            tempNode->Parent->Right = tempNode->Right;
                        }
                    }
                    else
                        m_Root = tempNode;
                }
                // now swap it out
                tempNode->Right = Node->Right;
                tempNode->Left = Node->Left;
                tempNode->Parent = Node->Parent;
                if (Node->Left)
                    Node->Left->Parent = tempNode;
                if (Node->Right)
                    Node->Right->Parent = tempNode;
            }
        }
        else
        {
            //no children, just point the parent at NULL
            if (Node->Parent)
            {
                if (Node->Parent->Chain == Node)
                {
                    Node->Parent->Chain = NULL;
                }
                else if (Node->Parent->Left == Node)
                {
                    Node->Parent->Left = NULL;
                }
                else if (Node->Parent->Right == Node)
                {
                    Node->Parent->Right = NULL;
                }
            }
            else
                m_Root = NULL;
        }

        delete Node;
        m_Length--;
        return deTRUE;
    }
    T* GetData(void* ptr)
    {
        TBSTNode * Node = (TBSTNode*)ptr;
        if (Node == NULL)
            return NULL;
        return &(Node->Data);
    }
    void GetDataPList(deTList <T*> &list)
    {
        if (m_Root)
            m_Root->AddDataToList(list);
    }
    void GetValueList(deTList <DWORD> &list)
    {
        if (m_Root)
            m_Root->AddValueToList(list);
    }
    long Length() const
    {
        return m_Length;
    }
    long size() const { return m_Length; }
    
    // iterator stuff
    inline iterator begin() {
        TBSTNode *Node = (TBSTNode*)m_Root;
        while (Node && Node->Left)
            Node = Node->Left;
        return iterator(Node);
    }
    inline iterator end()   { return iterator(0); }
    
    iterator insert(const T & data, const DWORD Val[N])
    {
        TBSTNode * Node = (TBSTNode*)AddElement(data, Val);
        return iterator(Node);
    }

    inline iterator erase(iterator& it)
    {
        iterator next = it;
        ++next;
        RemoveElement(it.m_Node);
        return next;
    }
};

//#pragma warning (default : 4710)

#endif

---